import os, sys

# 把包的父目录添加到系统搜索路径
BASE_DIR=os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
sys.path.append(BASE_DIR)

from base_data_structures.stack import Stack

# 表达式转换: 中缀转后缀
def infixToPostfix(infixexpr):
    # 记录操作符优先级
    prec = {}
    prec['*'] = 3
    prec['/'] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec['('] = 1

    opStack = Stack()
    postfixList = []
    tokenList = list(infixexpr)

    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            # 如果是操作数, 就直接添加到后缀表达式中
            postfixList.append(token)
        elif token=='(':
            # 如果是左括号, 就压栈
            opStack.push(token)
        elif token == ')':
            # 如果是右括号, 就反复出栈, 知道左括号为止
            topToken = opStack.pop()
            while topToken !='(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            # 如果是操作符, 首先要判断栈顶的操作符优先级是否高
            # 假如栈顶操作符优先级高,那么首先要出栈这个操作符, 添加到后缀表达式中
            while not opStack.isEmpty() and prec[opStack.peek()] >= prec[token]:
                postfixList.append(opStack.pop())
            # 否则直接压栈一个操作符
            opStack.push(token)

    # 将栈中剩余的操作符出栈, 加入后缀表达式中        
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return " ".join(postfixList)

# print(infixToPostfix("A+B*C"))